A database having thousands of entries often has complex structure. Hash table and tree structures (including B-trees) are common in the database art.
Navigating a database to find a particular database record is known to be a potentially time consuming process, typically requiring following multiple pointers and, in the case of a hash table structure, computing hash functions. Hash table structures also require searching for an exact match or empty location after indexing into a hash table. Hash table datastructures constructed with dynamically allocated memory may require following a considerable number of pointers to locate a record in the database. Following database structure to locate a particular record of a database is known herein as “walking” the database.
Adding a record to a database typically requires finding a parent or previous record in the database, allocating a new memory data record, then manipulating pointers to add the new record to the database. Similarly, deleting a record from a database requires knowledge of the location of the parent or previous record in the database, as well as the current record.
Many modern operating systems, including recent versions of Microsoft Windows, are multithreaded operating systems. These systems permit programs to be divided into multiple threads, each thread containing executable code and data that can be invoked independently of other threads by multitasking management code of the operating system. Typically, the operating system assigns a processor to execute a thread for a period of time, then interrupts execution of the thread and allows another thread to execute. Typically, code of a thread can share data with other threads of the program. These systems also permit part or all of the executable code to be common code, executed independently on separate data.
Multithreaded operating systems may also execute on multiple processors of a system. Threads may be assigned by the operating system to different processors for execution, therefore several threads may be executed simultaneously by the system, with each processor timeshared among yet more threads.
A firewall system requires a database of rules for filtering network communication packets as they are relayed through multiple network interfaces of the system. Packets are often associated with connections; it is known that threads may be associated with packets associated with particular connections through the firewall. A firewall structured in this way may have hundreds or thousands of threads each of which may receive execution resources at any time.
In a multithreaded environment, it is typically necessary to ensure that database structures are not changed by a first thread while a second thread modifies database structure, as happens when the second thread adds new records to, or deletes existing records from, the database. Simultaneous access by the first and second threads to database structure may cause database link corruption, leading to threads following an invalid link, resulting in access to random locations or uninitialized memory contents; a memory out-of-bounds error may also occur. A database-lock mechanism is typically used to prevent the first thread from accessing database structure while the second thread alters database structure. Once the second thread is done altering database structure, the first thread is permitted to access the database.
Database lock mechanisms may be exclusive, where exclusive access is obtained by a thread for reading or writing to database structure. Database lock mechanisms are also known that are nonexclusive for read, but exclusive for write, where lock for read prevents grant of lock for write.
A firewall connection and filter rule information database can require multiple accesses by a thread to the same record of the database; these accesses can be separated in time. A connection and filter rule information database can serve as a limit table as described in copending, cofiled, U.S. patent application Ser. No. 10/453,043. For example, it can be desirable to keep a count of connections through the firewall between particular upper level protocol (ULP) ports at particular Internet Protocol (IP) addresses in a connection database record. The ULP may be Transmission Control Protocol (TCP), User Datagram Protocol UDP, or a similar protocol. The ULP may involve layered protocols, such as Simple Mail Transfer Protocol (SMTP) which typically operates over port 25 of TCP. A connection database record used for counting current SMTP-over-TCP connections between particular IP addresses is accessed at least on initiation and completion of each SMTP-over-TCP connection.
Since walking a database can take considerable time, it is desirable to minimize the number of times per connection at which the database must be walked.